home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / sbprolog / amiga / v3_1 / sbp3_1e.lzh / QSORT.PL < prev    next >
Text File  |  1991-10-31  |  2KB  |  75 lines
  1. /* From the book PROLOG PROGRAMMING IN DEPTH
  2.    by Michael A. Covington, Donald Nute, and Andre Vellino.
  3.    Copyright 1988 Scott, Foresman & Co.
  4.    Non-commercial distribution of this file is permitted. */
  5.  
  6. /* QSORT.PL */
  7. /* Several versions of Quicksort */
  8.  
  9. /*
  10.  * partition(List,Pivot,Before,After)
  11.  *   Divides List into two lists, one
  12.  *   containing elements that should
  13.  *   come before Pivot, the other containing
  14.  *   elements that should come after it.
  15.  *   Used in all versions of Quicksort.
  16.  */
  17.  
  18. partition([X|Tail],Pivot,[X|Before],After) :-
  19.     X =< Pivot,
  20.     !,
  21.     partition(Tail,Pivot,Before,After).
  22.  
  23. partition([X|Tail],Pivot,Before,[X|After]) :-
  24.     X > Pivot,
  25.     !,
  26.     partition(Tail,Pivot,Before,After).
  27.  
  28. partition([],_,[],[]).
  29.  
  30.  
  31. /* Original Quicksort algorithm */
  32. /* (Sterling and Shapiro, 1986:56;
  33.    Clocksin and Mellish 1984:157) */
  34.  
  35. quicksort([X|Tail],Result) :-
  36.     !,
  37.     partition(Tail,X,Before,After),
  38.     quicksort(Before,SortedBefore),
  39.     quicksort(After,SortedAfter),
  40.     append(SortedBefore,[X|SortedAfter],Result).
  41.  
  42. quicksort([],[]).
  43.  
  44. append([],X,X).
  45. append([X|Tail],Y,[X|Z]) :- append(Tail,Y,Z).
  46.  
  47.  
  48. /* Quicksort with difference-lists */
  49. /* (Sterling and Shapiro 1986:244) */
  50.  
  51. dlqsort(List,Result) :- quicksort_dl(List,Result/[]).
  52.  
  53. quicksort_dl([X|Tail],Result/ResultTail) :-
  54.      !,
  55.      partition(Tail,X,Before,After),
  56.      quicksort_dl(Before,Result/[X|Z]),
  57.      quicksort_dl(After,Z/ResultTail).
  58.  
  59. quicksort_dl([],X/X).
  60.  
  61.  
  62. /* Improved Quicksort using stacks */
  63. /* (Kluzniak and Szpakowicz 1985;
  64.    Clocksin and Mellish 1984:157) */
  65.  
  66. iqsort(List,Result) :- iqsort_aux(List,[],Result).
  67.  
  68. iqsort_aux([X|Tail],Stack,Result) :-
  69.      !,
  70.      partition(Tail,X,Before,After),
  71.      iqsort_aux(After,Stack,NewStack),
  72.      iqsort_aux(Before,[X|NewStack],Result).
  73.  
  74. iqsort_aux([],Stack,Stack).
  75.